#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

/*
归并排序法
*/
double findMedianSortedArrays1(int *nums1, int nums1Size, int *nums2, int nums2Size)
{
    // 定义一个大的数组，将两个nums放到一起
    int *totalNums = malloc(sizeof(int) * (nums1Size + nums2Size));
    int numsPoint1 = 0; // 指针1
    int numsPoint2 = 0; // 指针2
    int index = 0;

    // 将两个子数组数据排序并赋值进总数组
    while (numsPoint1 < nums1Size && numsPoint2 < nums2Size)
    {
        if (nums1[numsPoint1] < nums2[numsPoint2])
        {
            totalNums[index++] = nums1[numsPoint1];
            numsPoint1++;
        }
        else
        {
            totalNums[index++] = nums2[numsPoint2];
            numsPoint2++;
        }
    }

    while (numsPoint1 < nums1Size)
    {
        totalNums[index++] = nums1[numsPoint1];
        numsPoint1++;
    }

    while (numsPoint2 < nums2Size)
    {
        totalNums[index++] = nums2[numsPoint2];
        numsPoint2++;
    }

    for (int i = 0; i < (sizeof(totalNums) / sizeof(int)); i++)
    {
        printf("%d\n", totalNums[i]);
    }
    printf("\n");

    return 0.0;
}

/*
归双指针
*/
double findMedianSortedArrays2(int *nums1, int nums1Size, int *nums2, int nums2Size)
{
    // 当一个数组为空，直接返回另一个数组的中位数
    if (nums1Size == 0)
    {
        if (nums2Size % 2 == 0)
        {
            return (double)(nums2[nums2Size / 2] + nums2[nums2Size / 2 - 1]) / 2;
        }
        else
        {
            return (double)nums2[nums2Size / 2];
        }
    }
    if (nums2Size == 0)
    {
        if (nums1Size % 2 == 0)
        {
            return (double)(nums1[nums1Size / 2] + nums1[nums1Size / 2 - 1]) / 2;
        }
        else
        {
            return (double)nums1[nums1Size / 2];
        }
    }

    int sum = nums1Size + nums2Size; // 两个数组总长
    int count = (sum - 1) / 2;       // 需要移除的数据个数
    int i = 0, j = 0;                // 双指针,i是nums1的，j是nums2的
    while (count > 0)
    {
        if (nums1[i] > nums2[j])
        { // 移除数据较小者
            j++;
        }
        else
        {
            i++;
        }
        count--;
        // 当一个数组为空，则计算并返回中位数
        // 说明一个数组的最小值大于另一个数组的最大值（我们称这种为不交融）
        if (i > nums1Size - 1)
        {
            int index = sum / 2 - nums1Size - 1;

            if (sum % 2 == 0)
            {
                return (double)(nums2[index] + nums2[index + 1]) / 2;
            }
            else
            {
                return (double)nums2[index + 1];
            }
        }
        if (j > nums2Size - 1)
        {
            int index = sum / 2 - nums2Size - 1;
            if (sum % 2 == 0)
            {
                return (double)(nums1[index] + nums1[index + 1]) / 2;
            }
            else
            {
                return (double)nums1[index + 1];
            }
        }
    }

    // 当两个数组数据交融，如果是奇数个数据则返回i,j对应数组中最小的那个值
    // 但是偶数个数据时我们需要注意：有可能未取到两个中位数
    if (sum % 2 == 0)
    {
        // 获取两个值
        int num1 = nums1[i];
        int num2 = nums2[j];
        if (num1 < num2 && i < nums1Size - 1)
        {
            // 判断第二个值是否为中位数
            num2 = nums1[i + 1] < num2 ? nums1[i + 1] : num2;
        }
        else if (num1 > num2 && j < nums2Size - 1)
        {
            // 判断第一个值是否为中位数
            num1 = nums2[j + 1] < num1 ? nums2[j + 1] : num1;
        }
        return (double)(num1 + num2) / 2;
    }
    else
    {
        return (double)nums1[i] > nums2[j] ? nums2[j] : nums1[i];
    }
    return 0;
}

int getKthElement(int *nums1, int nums1Size, int *nums2, int nums2Size, int k)
{
    int index1 = 0, index2 = 0;

    while (true)
    {
        // 边界情况
        if (index1 == nums1Size)
        {
            return nums2[index2 + k - 1];
        }
        if (index2 == nums2Size)
        {
            return nums1[index1 + k - 1];
        }
        // 将中位数左边的数全部删除了
        if (k == 1)
        {
            return nums1[index1] > nums2[index2] ? nums2[index2] : nums1[index1];
        }

        // 正常情况：获取下一个中位线左边数据的下标
        int newIndex1 = (index1 + k / 2 - 1) > (nums1Size - 1) ? nums1Size - 1 : (index1 + k / 2 - 1);
        int newIndex2 = (index2 + k / 2 - 1) > (nums2Size - 1) ? nums2Size - 1 : (index2 + k / 2 - 1);
        int pivot1 = nums1[newIndex1];
        int pivot2 = nums2[newIndex2];
        // 比较这两个数
        if (pivot1 <= pivot2)
        {
            k -= newIndex1 - index1 + 1;
            index1 = newIndex1 + 1;
        }
        else
        {
            k -= newIndex2 - index2 + 1;
            index2 = newIndex2 + 1;
        }
    }
}

/*
二分删除
*/
double findMedianSortedArrays3(int *nums1, int nums1Size, int *nums2, int nums2Size)
{
    int totalLength = nums1Size + nums2Size;
    if (totalLength % 2 == 1)
    {
        return getKthElement(nums1, nums1Size, nums2, nums2Size, (totalLength + 1) / 2); // 两个数组的总数为奇数
    }
    else
    {
        return (getKthElement(nums1, nums1Size, nums2, nums2Size, totalLength / 2) + getKthElement(nums1, nums1Size, nums2, nums2Size, totalLength / 2 + 1)) / 2.0; // 两个数组的总数为偶数
    }
}

/*
寻找两个正序数组的中位数

给定两个大小分别为 m 和 n 的正序（从小到大）数组nums1 和nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
*/
int main(int argc, char const *argv[])
{
#if 0
    int nums1[] = {1, 3};
    int nums2[] = {2};
#endif
#if 1
    int nums1[] = {1, 3};
    int nums2[] = {2};
#endif
    int nums1Size = sizeof(nums1) / sizeof(int);
    int nums2Size = sizeof(nums2) / sizeof(int);
#if 1
    long ret1 = findMedianSortedArrays1(nums1, nums1Size, nums2, nums2Size);
    printf("find median ret1 value = %ld\n", ret1);
#endif // 0
#if 0
    long ret2 = findMedianSortedArrays2(nums1, nums1Size, nums2, nums2Size);
    printf("find median ret2 value = %ld\n", ret2);
#endif // 0
#if 0
    long ret3 = findMedianSortedArrays3(nums1, nums1Size, nums2, nums2Size);
    printf("find median ret3 value = %ld\n", ret3);
#endif
    return 0;
}
